/**
 * https://leetcode.cn/problems/generate-parentheses/submissions/550462506/
 * 22.括号生成
 * medium 2024.07.28
 * dp
 */

class Solution {
public:
    vector<string> v;
    bool check(string& str){
        int b=0;
        for(char c:str){
            if(c=='(')
            b++;
            else
            b--;
            if(b<0)
            return false;
        }
        return b==0;
    }
    void dfs(string& str,int n){
        if(n==str.size()){
            if(check(str))
            v.push_back(str);
            return;
        }
        str+='(';
        dfs(str,n);
        str.pop_back();
        str+=')';
        dfs(str,n);
        str.pop_back();
    }
    vector<string> generateParenthesis(int n) {
        string str;
        dfs(str,n*2);
        return v;
    }
};